|
In mathematics, the Szpilrajn extension theorem, due to (later called Edward Marczewski), is one of many examples of the use of the axiom of choice (in the form of Zorn's lemma) to find a maximal set with certain properties. The theorem states that every strict partial order is contained into a total order, where: * a strict partial order is a irreflexive and transitive relation * a total order is a strict partial order that is also total Intuitively, the theorem states that a comparison between elements that leaves some pairs incomparable can be extended in such a way every element is either less than or greater than another. == Definitions and statement == A binary relation ''R'' over a set ''S'' is formally defined as a set of pairs of elements ''‹ x,y ›'' where ''x, y ∈ S''. The condition ''‹ x,y › ∈ R'' is generally abbreviated ''xRy''. A relation is irreflexive if ''xRx'' holds for no element ''x ∈ S''. It is transitive if ''xRy'' and ''yRz'' imply ''xRz''. It is total if either ''xRy'' or ''yRx'' holds for every pair of elements ''x'' and ''y'' of ''S''. If a relation ''R'' is contained in another ''T'' then every pair in the first is also in the second. As a result, ''xRy'' implies ''xTy'', which can be taken as an alternative definition of containment. The extension theorem tells that every relation ''R'' that is non-reflexive and transitive (a strict partial order) is contained in another ''T'' that is still non-reflexive and transitive but also total (a total order). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Szpilrajn extension theorem」の詳細全文を読む スポンサード リンク
|